package com.jia.leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: Leetcode
 * @description: 分割回文串II
 * @author: STU756
 * @create: 2020-08-10 01:28
 */
public class Pro0132 {
    //回文字符串，从小扫大范围
    public int minCut(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int j = 0; j < n; j++) {
            for(int i = j; i >= 0; i--) {
                dp[i][j] = s.charAt(i) == s.charAt(j) &&(i+1 >= j-1 || dp[i+1][j-1]);
            }
        }
        // for(int i = 0; i < n; i++) {
        //     System.out.println(Arrays.toString(dp[i]));
        // }
        int[] f = new int[n + 1];
        Arrays.fill(f, n + 1);
        f[0] = 0;
        for(int i = 1; i <= n; i++) {  // f[i] =  {f[i], f[j-1] + 1 ifdp[j][i] == true}
            for(int j = 1; j <= i; j++) {
                if(dp[j-1][i-1]) {
                    f[i] = Math.min(f[i], f[j-1] + 1);
                }
            }

        }
        // System.out.println(Arrays.toString(f));
        return f[n] - 1;
    }

    /**
     * 解题思想：根据131题可知能找出所有字符串每个子串都为回文串的集合，只需要对这些全集进行裁剪即可得到最小分割次数
     *  按照131题解法，只需在终止条件统计最小分割次数，但超时。
     *  需要对131题进行剪枝
     * @param s
     * @return
     */
    public int minCut2(String s) {
//        partition(s);
//        return minCuts;
        /**
         * 动态规划：dp[i]表示将0~i分割成子串，子串都为回文字符串的最小分割数
         * 状态计算：
         *  dp[i] = dp[i-1] + 1,当s[i]可以单独构成一个回文串
         *  只需判断s[k,i]是否为回文串，那么dp[i] = min(dp[i], dp[k-1] + 1) 如果s[k,i]是回文串
         */
        int n = s.length();
        boolean[][] check = new boolean[n + 1][n + 1];
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                check[i+1][j+1] = isPlalindrome(s, i, j);
            }
        }
        int[] dp = new int[n+1];
        dp[0] = -1;
        for(int i = 1; i <= n; i++) {
            dp[i] = dp[i-1] + 1;
            for(int k = 1; k < i; k++) {
                if(check[k][i]) {
                    dp[i] = Math.min(dp[i], dp[k-1] + 1);
                }
            }
        }
        return dp[n];
    }

    int minCuts;
    public void partition(String s) {
        if(s == null || s.length() == 0) return;
        this.minCuts = s.length();
        bracktracking(s, 0,new ArrayList<String>());
    }

    /**
     *
     * @param s  字符串
     * @param index  字符串开始下表
     * @param list    存储当前都是回文串的集合
     */
    private void bracktracking(String s, int index, List<String> list ){
        //1.终止条件
        if(index == s.length()) {
            //判断一下是否最小
            minCuts = Math.min(minCuts, list.size() - 1);
            return;
        }
        for(int i = index; i < s.length(); i++) {
            if(!isPlalindrome(s, index, i)) { //进行剪枝
                continue;
            }

            //2.选择
            list.add(s.substring(index, i + 1));
            if(list.size() >= minCuts) return;
            //3.drill down 下一层
            bracktracking(s, i+1, list);
            //4.撤销
            list.remove(list.size() - 1);
        }
    }
    //判断字符串str，对应下表[st..ed]是否为回文字符串
    private boolean isPlalindrome(String str, int st, int ed) {
        if(st > ed) return false;
        while(st <= ed) {
            if(str.charAt(st) != str.charAt(ed)) {
                return false;
            }
            ++st;
            --ed;
        }
        return true;
    }
}
